package zuoshen_video;

import java.util.*;
import java.util.stream.Collector;
import java.util.stream.Collectors;

import org.junit.Test;

import utils.ArrayGenerator;

//递归问题
public class RecurrsionToDynamicProblems {
    
    class StackReverse{
        //如何不利用额外的空间，只利用递归使得栈逆序？
        public Stack<Integer> reverseStack(Stack<Integer> stack) {
            //其实最好还是写成空位置，防止没有元素
            if (stack.isEmpty()) return stack;
            if (stack.size() == 1) return stack;//只剩一个元素时，必须最顶部的元素，放在栈底没有问题
            int cur = getBottomElement(stack);//暂存栈底元素
            reverseStack(stack); //一个黑箱子，能讲剩下的栈中元素逆序。
            //将栈底元素放在栈顶
            stack.push(cur);
            return stack;
        }

        //不利用额外空间，只利用递归，取出栈底的元素，且底部之上的元素相对位置都不改变
        public int getBottomElement(Stack<Integer> stack) {
            if (stack.size() == 1) return stack.pop();
            int cur = stack.pop(); //暂存当前栈顶元素
            int res = getBottomElement(stack);
            stack.push(cur);//取出底部元素后，将原来的栈顶元素返回栈顶
            return res; 
        }
    }

    @Test
    public void test1() {
        Stack<Integer> stack = new Stack<>();
        StackReverse sr = new StackReverse();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        System.out.println(stack);
        System.out.println(sr.reverseStack(stack));
        System.out.println(sr.getBottomElement(stack));
        System.out.println(stack);
    }


    //得到所有的子序列
    class SubSequence {
        //每个位置的数字不重复
        public List<List<Integer>> subSequence (int[] nums) {
            if (nums == null || nums.length == 0)  return new ArrayList<>();
            dfs(nums, 0, new LinkedList<>());
            return res;
        }
        List<List<Integer>> res = new ArrayList<>();
        public void dfs(int[] nums, int idx, LinkedList<Integer> cur) {
            if (idx == nums.length) {
                res.add(new LinkedList<>(cur));
                return;
            }
            //不要当前位置
            dfs(nums, idx + 1, cur);
            cur.addLast(nums[idx]);
            dfs(nums, idx + 1, cur);//要当前位置
            cur.removeLast();
        }
        //存在重复数字，要求得到的结果永不相同，添加一个set作为当前已经选择的元素
        public List<List<Integer>> subUnsameSequence (int[] nums) {
            return dfs2(nums, 0, new LinkedList<>(), new HashSet<>(), new ArrayList<>());    
        }
        //对捂住，这个只有String的set可以做到，序列只能遍历了。。。
        public List<List<Integer>> dfs2(int[] nums, int idx, Deque<Integer> cur, Set<Integer> set, List<List<Integer>> res) {
            if (idx == nums.length) {
                res.add(new ArrayList<>(cur));
                return res;
            }
            //当前未选择，才能添加
            if (!set.contains(nums[idx])) {

            }
            return res;
        }

        //得到元素数组的全排列[可能重复],来试试置换吧。。
        //重复还是需要Set去重。
        public List<List<Integer>> findAllPermutations(int[] nums) {
            dfs3(nums, 0);
            System.out.println(ans.size());
            // System.out.println(new HashSet<>(ans).size());
            Set<List<Integer>> set = new HashSet<>();
            int count = 0, c1 = 0;
            for (int i = 0; i < ans.size(); i++) {
                if (set.contains(ans.get(i))) {
                    System.out.print(ans.get(i));
                    count++;
                }
                if (ans.get(i).get(0) == 2) c1++;
                set.add(ans.get(i));
            }
            System.out.println(count);
            System.out.println(c1);
            return ans;
        }
        List<List<Integer>> ans = new ArrayList<>();
        public void dfs3(int[] nums, int idx) {
            if (idx == nums.length) {
                ans.add(Arrays.stream(nums).boxed().collect(Collectors.toList()));
                return;
            }
            //这就是分支限界
            Set<Integer> set = new HashSet<>();//存储当前遍历到的元素，防止同样的元素进行置换
            for (int i = idx; i < nums.length; i++) {
                if (!set.contains(nums[i])) {
                    set.add(nums[idx]);
                    swap(nums, i, idx);
                    dfs3(nums, idx + 1);
                    swap(nums, i, idx);//在交换回来，防止分支污染
                }
            }

            //字符串的全排列就可以用上面的
            class Solution {
                List<String> res = new ArrayList<>();
                public String[] permutation(String s) {
                    if (s == null || s.length() == 0)  return new String[0];
                    dfs(s.toCharArray(), 0);
                    return res.toArray(new String[res.size()]);
                }

                public void dfs(char[] chs, int idx) {
                    if (idx == chs.length) {
                        res.add(new String(chs));
                        return;
                    }
                    Set<Character> set = new HashSet<>();
                    for (int i = idx; i < chs.length; i++) {
                        if (!set.contains(chs[i])) {
                            set.add(chs[i]);
                            swap(chs, i, idx);
                            dfs(chs, idx + 1);
                            swap(chs, i, idx);
                        }
                    }
                }
                public void swap(char[] nums, int i, int j) {
                    char temp = nums[i];
                    nums[i] = nums[j];
                    nums[j] = temp;
                }
            }
        }

        public void swap(int[] nums, int i, int j) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    }

    @Test
    public void test2() {
        SubSequence ss = new SubSequence();
        int nums[] =  {1, 2, 2, 4, 5};
        System.out.println(ss.findAllPermutations(nums));
    }

    //将编码为数字的字符串转换为原串，注意一个编码可能有多种解读："12" => L或者AB
    class StringDecoder {

        public List<String> decode(String s) {
            dfs(s, 0, new StringBuilder());
            return res;
        }

        //只返回数量，不返回结果，用于改动态规划
        public int dfs2 (String s, int idx) {
            if (idx == s.length()) return 1;
            if (s.charAt(idx) == '0') return 0; //一旦步入0，不能转化
            int res = 0;
            res += dfs2(s, idx + 1);//一个字符可以直接改
            if (idx < s.length() - 1) {
                char[] chs = s.substring(idx, idx + 2).toCharArray();
                int num = (int)(chs[0] - '0') * 10 + chs[1] - '0';
                if (num <= 26) res += dfs2(s, idx + 2);
            }
            return res;
        }

        /* 
            1.变化量：idx
            2.范围：0 ~ len
            3.转移方程：f[i] = f[i + 1]; if (....) f[i] += f[i + 2]
            4.目标: f[0] -> f[len], f[len] = 1
        */
        public int decodeNums(String s) {
            int len = s.length();
            int[] f = new int[len + 1];
            f[len] = 1;
            for (int i = len - 1; i >= 0; i--) {
                if (i > 0 && s.charAt(i - 1) == '0') f[i] = 0;
                else {
                    f[i] = f[i + 1];
                    if (i != len - 1) {
                        char[] chs = s.substring(i, i + 2).toCharArray();
                        int num = (chs[0] - '0') * 10 + chs[1] - '0';
                        if (num <= 26) {
                            f[i] += f[i + 2];
                        }
                    }
                }
            }
            return f[0];
        }

        public int decodeNums2(String s) {
            int len = s.length(), lastTwo = 0, lastOne = 1;
            for (int i = len - 1; i >= 0; i--) {
                if (i >= 1 && s.charAt(i - 1) == '0') {
                    lastTwo = lastOne;
                    lastOne = 0;
                } else {
                    int temp = lastTwo;
                    lastTwo = lastOne;
                    // lastOne = lastTwo;
                    if (i != len - 1) {
                        char[] chs = s.substring(i, i + 2).toCharArray();
                        int num = (chs[0] - '0') * 10 + chs[1] - '0';
                        if (num <= 26) {
                            lastOne += temp;
                        }
                    }
                }

            }
            return lastOne;
        }

        List<String> res = new ArrayList<>();
        public void dfs(String s, int idx, StringBuilder sb) {
            if (idx == s.length()) {
                res.add(sb.toString());
                return;
            }
            //需要处理s[i] == '0'的basecase，这种情况下，不可能进行转换
            if (s.charAt(idx) == '0') return;//直接结束这条分支。

            //此外，parse()也处理了大于26的情况，这也会直接跳过if，返回。

            //解码一个字符
            sb.append(parse(s.substring(idx, idx + 1)));
            dfs(s, idx + 1, sb);
            sb.deleteCharAt(sb.length() - 1);

            //解码两个字符
           if (idx != s.length() - 1) {
                String t = parse(s.substring(idx, idx + 2));
                if (t != null) {
                    sb.append(t);
                    dfs(s, idx + 2, sb);
                    sb.deleteCharAt(sb.length() - 1);
                }
           }
        }

        public String parse(String s) {
            if (s.length() == 1) return (char)(s.charAt(0) - '1' + 'A') + "";
            else {
                int sit = Integer.parseInt(s);
                if (sit > 26) return null;
                else return "" + (char)(sit - 1 + 'A');
            }
        }
     }

     @Test
     public void test3() {
        StringDecoder sd = new StringDecoder();
        System.out.println(sd.decode("101"));
        System.out.println(sd.dfs2("1111", 0));
        System.out.println(sd.decodeNums("11111"));
        System.out.println(sd.decodeNums2("11111"));
     }

     class BackpackProblem {
         public int oneZeroBackpack(int[] weight, int[] value, int v) {
             dfs (0, weight, value, 0, v);
             int max = Integer.MIN_VALUE;
             for (int i = 0; i < res.size(); i++) {
                max = Math.max(max, res.get(i));
             }
             return max;
         }

         List<Integer> res = new ArrayList<>();
         public void dfs (int idx, int[] w, int[] value, int cur, int vac) {
            if (idx == w.length) {
                res.add(cur);
                return;
            }
            //选择当前
            if (w[idx] <= vac) dfs(idx + 1, w, value, cur + value[idx], vac - w[idx]);
            // 不选择
            dfs(idx + 1, w, value, cur, vac);
         }
     }

     class BackpackProblem2 {
        public int oneZeroBackpack(int[] weight, int[] value, int v) {
            dfs (0, weight, value, 0, v);
            int max = Integer.MIN_VALUE;
 
            return max;
        }

        //也可以在一个方法中返回最大价值，而无序遍历结果
        public int dfs (int idx, int[] w, int[] value, int cur, int vac) {
           if (idx == w.length) {
               return cur;
           }
           //选择当前
           int selected = 0;
           if (w[idx] <= vac) selected = dfs(idx + 1, w, value, cur + value[idx], vac - w[idx]);
           // 不选择
           int unselected = dfs(idx + 1, w, value, cur, vac);
           return Math.max(selected, unselected);
        }
    }

     @Test
     public void test4() {
        int[] n1 = {1, 2, 3};
        int[] n2 = {1, 2, 3};
        StringBuilder sb = new StringBuilder();
        Arrays.stream(n1).forEach((n) -> sb.append(n + ","));
        StringBuilder sb2 = new StringBuilder();
        Arrays.stream(n1).forEach((n) -> sb2.append(n + ","));
       Set<String> set = new HashSet<>();
       set.add(new String("小明,11,男"));
       set.add("小明,11,男");
       set.add(new StringBuilder("小明,11,男").toString());
       User u1 = new User("小明", 11, "男");
       Map<String, Integer> map = new HashMap<>();
       map.put(u1.toString(), 1);
       User u2 = new User("小明", 11, "男");
       System.out.println(map.get(u2.toString()));
       set.add(u1.toString());
       set.add(u2.toString());
       System.out.println(set);
     }

     class User {
         String name;
         int age;
         String gender;
         public User(String name, int age, String gender) {
             this.name = name;
             this.age = age;
             this.gender = gender;
         }

         public String toString() {
             return this.name + "," + this.age + "," + this.gender;
         }
     }


     //两个依次拿一个数组左右两边求和，直到拿完，返回胜者的分数
     class CardGeme {
        public int win(int[] nums) {
            return dfs(nums, 0, nums.length - 1, 0, 0, true);
        }

        //lo、hi是当前可以拿的两端
        //resA/resB是两名玩家当前的得分
        public int dfs (int[] nums, int lo, int hi, int resA, int resB, boolean isA) {
            if (lo > hi) return Math.max(resA, resB);
            // int max = Math.max(nums[lo], nums[hi]);
            int chooseLo = 0, chooseHi = 0;
            if (isA) {
               chooseLo = dfs(nums, lo + 1, hi, resA + nums[lo], resB, !isA);
               if (hi < nums.length - 1) chooseHi = dfs(nums, lo, hi + 1, resA + nums[hi], resB, !isA);
            } else {
                chooseLo = dfs(nums, lo + 1, hi, resA, resB + nums[lo], !isA);
                if (hi < nums.length - 1)  chooseHi = dfs(nums, lo, hi + 1, resA, resB + nums[hi], !isA);
            }
            return Math.max(chooseLo, chooseHi);
        }

        //使用双递归方法来博弈
        public int win2(int[] nums) {
            //可能名称引入误解：myTurn是指先拿的那个玩家所能得的分，yourTurn是后拿... 从两名玩家中选择最大值
            return Math.max(myTurn(nums, 0, nums.length - 1), yourTurn(nums, 0, nums.length - 1));
        }

        public int myTurn(int[] nums, int lo, int hi) {
            if (lo == hi) return nums[lo];
            //从拿到左边和右边中选取最大值
            int left =  nums[lo] + yourTurn(nums, lo + 1, hi); //对方的选择区间被压榨到(lo + 1, hi)
            int right = nums[hi] + yourTurn(nums, lo, hi - 1);//...(LO, HI - 1)
            return Math.max(left, right);
        }

        //这个方法是站在我的视角看对方的操作，对方的选择不会加入我的收益，且对方只会让我收益最小
        public int yourTurn(int[] nums, int lo, int hi) {
            if (lo == hi) return 0; //只剩下一个被对方直接拿走
            int left = myTurn(nums, lo + 1, hi);
            int right = myTurn(nums, lo, hi - 1);
            return Math.min(left, right);
        }

        /* 
            1. 变量： lo:[0, len - 1], hi[0, len - 1], 谁的回合[使用两个动态数组]
            2. 结束：lo == hi， f[lo][hi] = nums[lo], s[lo][hi] = 0
            3. 目标：f[0][len - 1], s[0][len - 1] -> f[?][?], s[?][?] 
            【？相等，因此f[?][?]全为已知量，所求为f[0][len - 1]..s[0][len - 1]最大值
            4. 转移方程：f[lo][hi] = Math.max(s[lo][hi - 1] + nums[hi], s[lo + 1][hi] + nums[lo]),
             s[lo][hi] = Math.min(f[lo + 1][hi], f[lo][hi - 1])
        */
        public int win3(int[] nums) {
            int len = nums.length;
            int[][] f = new int[len][len], s = new int[len][len];
            //f[?][?]初始化为nums[?],s[?][?]默认为0
            for (int i = 0; i < len; i++) f[i][i] = nums[i];

            for (int i = 0; i < len; i++) {
                for (int j = 0; j < len; j++) {
                    if (i >= j) continue;
                    if (i == 0) {
                        f[i][j] = s[i][j - 1] + nums[j];
                        s[i][j] = f[i][j - 1];
                    } else if (j == len - 1) {
                        f[i][j] = s[i + 1][j] + nums[i];
                        s[i][j] = f[i + 1][j];
                    } else {
                        f[i][j] = Math.max(s[i][j - 1] + nums[j], s[i + 1][j] + nums[i]);
                        s[i][j] = Math.min(f[i][j - 1], f[i + 1][j]);
                    }
                }
            }
            return Math.max(s[0][len - 1], f[0][len - 1]);
        }

        /* 
            试试看三维
        */
        public int win4(int[] nums) {
            int len = nums.length;
            //为0表示我回合，1表示对方回合
            int[][][] f = new int[len][len][2];
            for (int i = 0; i < len; i++) {
                f[i][i][0] = nums[i];
                //另一组默认为0
            }

            for (int i = 0; i < len; i++) {
                for (int j = 0; j < len; j++) {
                    if (i == j) continue;
                    if (i == 0) {
                        f[i][j][0] = f[i][j - 1][1] + nums[j];
                        f[i][j][1] = f[i][j - 1][0];
                    } else if (j == len - 1) {
                        f[i][j][0] = f[i + 1][j][1] + nums[i];
                        f[i][j][1] = f[i + 1][j][0];
                    } else {
                        f[i][j][0] = Math.max(f[i][j - 1][1] + nums[j], f[i + 1][j][1] + nums[i]);
                        f[i][j][1] = Math.min(f[i][j - 1][0], f[i + 1][j][0]);
                    }
                }
            }
            return Math.max(f[0][len - 1][0], f[0][len - 1][1]);
        }
     }

     @Test
     public void test5() {
         CardGeme ag = new CardGeme();
         int[] nums = {70,100,1,4,5};
         boolean corrent = true;
         int temp;
         for (int i = 0; i < 145500000; i++) {
             nums = ArrayGenerator.getArray(100, (int)Math.random() * 20 + 1);
             if (ag.win(nums) != (temp = ag.win2(nums)) || ag.win3(nums) != temp) {
                 System.out.println(Arrays.toString(nums));
                 corrent = false;
             }
         }
         System.out.println(corrent == true ? "nice" : "fuck");       
     }

     //N皇后问题
     class NQueenProblem {
            public List<List<String>> nQueen(int n) {
                int[] nums = new int[n + 1];
                dfs(1, nums);
                System.out.println(res.size());
                return res;
            }
            List<List<String>> res = new ArrayList<>();
            public void dfs(int idx, int[] nums) {
                int n = nums.length - 1;
                if (n + 1 == idx) {
                    //到达棋盘外面，证明此方案可以通过，将之前存储的方案转化为棋盘排列
                    List<String> list = new ArrayList<>();
                    for (int i = 1; i <= n; i++) {
                        StringBuilder sb = new StringBuilder();
                        for (int j = 1; j <= n; j++) {
                            if (j == nums[i]) sb.append("Q");
                            else sb.append("*");
                        }
                        list.add(sb.toString());
                    }
                    res.add(list);
                    return;
                }
                
                for (int i = 1; i <= n; i++) {
                    nums[idx] = i;
                    if (isCorrect(nums, idx)) {
                        dfs(idx + 1, nums);
                    }
                }
            }

            public boolean isCorrect(int[] nums, int idx) {
                for (int i = 1; i < idx; i++) {
                    if (i == idx || nums[i] == nums[idx] || Math.abs(i - idx) == Math.abs(nums[i] - nums[idx])) return false;
                }
                return true;
            }


         

     }

     public  class NQueueBits {
        public int nQueen(long n) {
            return backtrack(n == 64 ? -1L : (1 << n) - 1L, 0L, 0L, 0L); //将最低n为置为1，用于验证最终解
        }

        public int backtrack(long limit, long colum, long left, long right) {
            if (limit == colum) return 1;//列全部放置了皇后，证明完成了全部行的摆放
            //记录到达这里可以成功的总的方案数
            int res = 0;
            long conditions = colum | left | right;
            long chooses = ~conditions & limit; //将限制条件取反，取有效位，就是可以选择放置的位置
            long rightestPos = 0L;

            while (chooses != 0) {
                rightestPos = ~(chooses - 1) & chooses; //从右往左一次选择一个位置放置皇后
                chooses ^= rightestPos;//去掉最右位已经选择过的方案
                res += backtrack(limit, 
                colum | rightestPos, //更新列限制：相应位置直接置为1
                (left | rightestPos) << 1, //更新左斜线限制 
                (right | rightestPos) >>> 1);//更新右斜线限制
            }
            return res;
        }
    }

    public  class NQueueBits2 {

        public List<List<String>> nQueen(long n) {
            backtrack(n == 64 ? -1L : (1 << n) - 1L, 0L, 0L, 0L, new LinkedList<>()); //将最低n为置为1，用于验证最终解
            return res;
        }

        List<List<String>> res = new ArrayList<>();
        public int backtrack(long limit, long colum, long left, long right, Deque<Long> deque) {
            if (limit == colum) {//列全部放置了皇后，证明完成了全部行的摆放 
                long cur;
                int pos, n;
                List<String> list = new ArrayList<>();
                Deque<Long> deque2 = new LinkedList<>(deque);
                while (!deque2.isEmpty()) {
                    StringBuilder sb = new StringBuilder();
                    cur = deque2.pollFirst();
                    n = deque.size();
                    pos = 1;
                    while (n > 0) {
                        if ((cur & pos) == 0) sb.insert(0, "*");
                        else sb.insert(0, "Q");
                        pos <<= 1;
                        n--;
                    }
                    list.add(sb.toString());
                }
                res.add(list);
                return 1;
            }
            //记录到达这里可以成功的总的方案数
            int res = 0;
            long conditions = colum | left | right;
            long chooses = ~conditions & limit; //将限制条件取反，取有效位，就是可以选择放置的位置
            long rightestPos = 0L;

            while (chooses != 0) {
                rightestPos = ~(chooses - 1) & chooses; //从右往左一次选择一个位置放置皇后
                chooses ^= rightestPos;//去掉最右位已经选择过的方案
                deque.addLast(rightestPos);
                res += backtrack(limit, 
                colum | rightestPos, //更新列限制：相应位置直接置为1
                (left | rightestPos) << 1, //更新左斜线限制 
                (right | rightestPos) >>> 1,//更新右斜线限制
                deque);
                deque.removeLast();
            }
            return res;
        }
    }


     @Test
     public void test6() {
        NQueueBits2 nqb = new NQueueBits2();
        long n = 4;
        int i = 4;
        NQueenProblem nq = new NQueenProblem();
        List<List<String>> res = nqb.nQueen(8);
        System.out.println(res.size());
        for (i = 0; i < res.size(); i++) {
            List<String> strs = res.get(i);
            System.out.println("========================");
            for (int j = 0; j < strs.size(); j++) {
                System.out.println(strs.get(j));
            }
            System.out.println("========================");
        }
        
        // while (n < 20) {
        //     long start1 = System.currentTimeMillis();
        //    System.out.print(nqb.nQueen(n++) + "====>");
        //    long end1 = System.currentTimeMillis();
        //    System.out.println(end1 - start1);
        //    long start2 = System.currentTimeMillis();
        // //    System.out.print(nq.nQueen(i++) + "===>");
        //    long end2 = System.currentTimeMillis();
        // //    System.out.println(end2 - start2);
        // }
     }

     class VillageLetter {
         public int getKinds(int n) {
             int[] f = new int[n + 1];
             f[1] = 0;
             f[2] = 1;
             f[3] = 2;
             for (int i = 4; i <= n; i++) {
                 f[i] = (i - 1) * (f[i - 1] + f[i - 2]);
             }
             return f[n];
         }
     }

     @Test
     public void test7() {
         VillageLetter vl = new VillageLetter();
         System.out.println(vl.getKinds(5));
     }

     @Test
     public void test(){
        NQueenProblem nq = new NQueenProblem();
        // System.out.println(nq.nQueen(4));
        long start = System.currentTimeMillis();
        // System.out.println(nq.nQueen(8));
        long mid = System.currentTimeMillis();
        System.out.println(mid - start);
     }

     class RobotWalk {
         /**
          * 机器人从m出发，必须走够k步的情况下，走到p位置的方案数。如起始为p + 1， p + 1 => p + 2 => p + 1 => p  就是一种方案
          * @param n 数列的总长度 n = 7对应 1,2,3,4,5,6,7, 到了1时只能走倒2，到了7只能走到6，在中间可以左右两边。
          * @param m 数组起点。
          * @param p 终点。
          * @param k 必须走够的步数。
          * @return 总的方案数
          */
         public int walk(int n, int m, int p, int k) {
            return dfs(n, m, p, k, 0, m);
         }

         public int dfs(int n, int m, int p, int k, int cur, int pos) {
            if (cur == k) return p == pos ? 1 : 0;
            int res = 0;
            if (pos == 1)  res += dfs(n, m, p, k, cur + 1, pos + 1);
            else if (pos == n) res += dfs(n, m, p, k, cur + 1, pos - 1);
            else res += (dfs(n, m, p, k, cur + 1, pos + 1) + dfs(n, m, p, k, cur + 1, pos - 1));
            return res;
         }

         //改为动态规划
         /* 
            1. 改变量：走过的步数cur, 当前位置pos;
            2. 变化范围：0 ~ k, 1 ~ n
            3. 终止状态：f[k][p] = 1,其他f[k][!p] = 0
            4. 递归表达式，....
            5. 目标【返回】：从f[0][m]到达f[k][p],因此最终状态为f[0][m]
         */
        public int walk2(int n, int m, int p, int k) {
            int[][] f = new int[k + 1][n + 1];
            f[k][p] = 1; //f[k][!p] 默认为0
            for (int i = k - 1; i >= 0; i--) {
                for (int j = 1; j <= n; j++) {
                    if (j == 1) f[i][j] = f[i + 1][j + 1];
                    else if (j == n) f[i][j] = f[i + 1][j - 1];
                    else f[i][j] = f[i + 1][j + 1] + f[i + 1][j - 1];
                }
            }
            return f[0][m];
        }
     }

     @Test
     public void test8() {
        RobotWalk rw = new RobotWalk();
        int res = rw.walk2(7, 2, 3, 3);
        System.out.println(res);
     }

     //记忆化搜索与动态规划的不同
     class AccountMoney {
         //使用nums[],每个位置的数字可以用任意次【包括0】，使得凑齐target的方案数
         public int account(int[] nums, int target) {
             if (nums == null || nums.length == 0 || target < 0) return 0;
             return dfs(nums, target, 0, 0);
         }

         public int dfs(int[] nums, int target, int idx, int cur) {
            //  if (cur > target) return 0; //某一个时刻，cur + nums[idx] * n > target, 按照判别条件是不会这样的
             if (idx == nums.length) return cur == target ? 1 : 0;
             int res = 0, sum;
             for (int i = 0; (sum = i * nums[idx] + cur) <= target; i++) {
                res += dfs(nums, target, idx + 1, sum);
             }
             return res;
         }

         public int account2(int[] nums, int target) {
            if (nums == null || nums.length == 0 || target < 0) return 0;
            f = new int[nums.length + 1][target + 1];
            for (int i = 0; i < nums.length; i++) {
                Arrays.fill(f[i], -1);
            }
            return dfs2(nums, target, 0, 0);
        }
        int[][] f;
        public int dfs2(int[] nums, int target, int idx, int cur) {
            // if (cur > target) return 0; //某一个时刻，cur + nums[idx] * n > target, 按照判别条件是不会这样的
            if (idx == nums.length) return cur == target ? 1 : 0;
            if (f[idx][cur] != -1) return f[idx][cur];
            int res = 0, sum;
            for (int i = 0; (sum = i * nums[idx] + cur) <= target; i++) {
               res += dfs2(nums, target, idx + 1, sum);
            }
            f[idx][cur] = res;
            return res;
        }

        public int account3(int[] nums, int target) {
            int len, sum;
            if (nums == null || (len = nums.length) == 0 || target < 0) return 0;
            f = new int[len + 1][target + 1];
            f[len][target] = 1;
            for (int i = len - 1; i >= 0; i--) {
                for (int j = 0; j <= target; j++) {
                    for (int k = 0; (sum = k * nums[i] + j) <= target; k++) {
                        f[i][j] += f[i + 1][sum];
                    } 
                }
            }
            return f[0][0];
        }

        public int account4(int[] nums, int target) {
            int len, sum;
            if (nums == null || (len = nums.length) == 0 || target < 0) return 0;
            f = new int[len + 1][target + 1];
            f[len][target] = 1;
            for (int i = len - 1; i >= 0; i--) {
                //在这里，只有j + nums[i] > target时，会使得这一层毫无推导空间，在其他时候，之前累计的值是可以直接传给后面的位置的
                for (int j = target; j >= 0; j--) {
                    if (j + nums[i] > target) f[i][j] = f[i + 1][j];
                    else f[i][j] = f[i + 1][j] + f[i][j + nums[i]];
                }
            }
            return f[0][0];
        }
     }

     @Test
     public void test9() {
         AccountMoney am = new AccountMoney();
         int[] nums = {5, 10, 50, 100};
         long s1 = System.currentTimeMillis();
         System.out.println(am.account(nums, 10000));
        long s2 = System.currentTimeMillis();
        System.out.println("test1:" + (s2 - s1));
        long s3 = System.currentTimeMillis();
        System.out.println(am.account2(nums, 10000));
        long s4 = System.currentTimeMillis();
        System.out.println("test2:" + (s4 - s3));
        long s5 = System.currentTimeMillis();
        System.out.println(am.account3(nums, 10000));
        long s6 = System.currentTimeMillis();
        System.out.println("test3:" + (s6 - s5));
        long s7 = System.currentTimeMillis();
        System.out.println(am.account4(nums, 10000));
        long s8 = System.currentTimeMillis();
        System.out.println("test4:" + (s8 - s7));
     }
}
